import java.util.*;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 中等
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
 * 返回满足题意的二叉搜索树的种数。
 * 输入：n = 3
 * 输出：5
 * @since 2023-09-17 10:33
 */
public class _096不同的二叉搜索树 {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(numTrees(n));
    }
    //动规
    public static int numTrees(int n) {
        /*
        G(n): 长度为 n的序列能构成的不同二叉搜索树的个数。
        F(i,n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)。
        */

        /*
        给定序列 1⋯n,我们选择数字 i作为根，
        则根为 i的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，
        对于笛卡尔积中的每个元素，加上根节点之后形成完整的二叉搜索树
         */
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                //G(n)和序列的内容无关，只和序列的长度有关
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
    //数学
    /*
    C(0) = 1
    C(i+1) = 2(2n+1)/(n+2) * C(i)
     */
    public int numTrees1(int n) {
        // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }
}
//超时
class Solution96 {
    int[] nums = new int[20];
    int len;
    public int numTrees(int n) {
        this.len = n;
        for(int i = 0; i < n; i++){
            nums[i] = i + 1;
        }
        set = new HashSet<>();
        indexToVal = new HashMap<>();
        dfs(0);
        return set.size();
    }
    Set<String> set;
    Map<Integer, Integer> indexToVal;
    private void buildTree(){
        indexToVal.clear();
        for(int i = 0; i < len; i++){
            build(0, nums[i]);
        }
        StringBuilder builder = new StringBuilder();
        Set<Integer> keySet = indexToVal.keySet();
        List<Integer> keys = new ArrayList<>(keySet);
        Collections.sort(keys);
        for(int key : keys){
            builder.append(indexToVal.get(key));
        }
        set.add(builder.toString());
    }
    //根据序列构建排序二叉树
    private void build(int index, int val){
        if(!indexToVal.containsKey(index)){
            indexToVal.put(index, val);
            return;
        }
        if(val < indexToVal.get(index)){
            build(2 * index + 1, val);
        }else{
            build(2 * index + 2, val);
        }
    }
    //全排列
    public void dfs(int index){
        if(index >= len){
            buildTree();
            return;
        }
        for(int i = index; i < len; i++){
            swap(i, index);
            dfs(index + 1);
            swap(i, index);
        }
    }
    private void swap(int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}